package xyz.robinbingo.leetcode.a20.b06.c17;

public class Solution {
    public int maxScoreSightseeingPair(int[] A) {
        if (A == null || A.length < 2) {
            return 0;
        }
        int length = A.length;
        int max = 0;
        int[] dp = new int[length];
        for (int i = 0; i < length; i++) {
            max = Math.max(max, A[i] + i);
            dp[i] = max;
        }
        int result = 0;
        for (int j = 1; j < length; j++) {
            result = Math.max(result, A[j] - j + dp[j - 1]);
        }
        return result;
    }
}